package algotithm.weekendrace.leetcode230.test4;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/28-10:27
 */
public class Solution {
    final int INF = (int) 1e9;
    public double[] getCollisionTimes(int[][] cars) {
        int n = cars.length;
        double res[] = new double[n];
        Arrays.fill(res, -1.0);
        PriorityQueue<double[]> pq = new PriorityQueue<>( (p1, p2) -> p1[2] < p2[2] ? -1 : 1);
        for(int i = 1; i < n; i++) {
            double time = INF;
            if(cars[i - 1][1] > cars[i][1]) {
                time = 1.0 * (cars[i][0] - cars[i - 1][0]) / (cars[i - 1][1] - cars[i][1]);
                pq.add(new double[]{i - 1, i, time});
            }
        }
        //System.out.println("pq");
        //for(double[] iii : pq) System.out.println(Arrays.toString(iii));
        int[] pre = new int[n];
        int[] post = new int[n];
        for(int i = 1; i < n; i++) {
            pre[i] = i - 1;
        }
        for(int i = 0; i < n - 1; i++) {
            post[i] = i + 1;
        }
        while(!pq.isEmpty()) {
            double[] cur = pq.poll();
            int i = (int) cur[0], j = (int) cur[1];
            double time = cur[2];
            //System.out.println("merge: " + i + " " + j + " " + time);
            if(res[i] >= 0 || res[j] >= 0) {
                continue;
            }
            res[i] = time;
            post[pre[i]] = j;
            pre[j] = pre[i];
            if(i > 0 && cars[pre[i]][1] > cars[j][1]) {
                time = 1.0 * (cars[j][0] - cars[pre[i]][0]) / (cars[pre[i]][1] - cars[j][1]);
                pq.add(new double[]{pre[i], j, time});
            }
            /*System.out.println("pq");
            for(double[] iii : pq) System.out.println(Arrays.toString(iii));
            System.out.println("pre: " + Arrays.toString(pre));*/
        }
        //System.out.println("");
        return res;
    }
}
